package tree;

import javax.tools.FileObject;
import java.io.*;
import java.util.*;

public class huffnanCode {
    static Map<Byte,String> huffnanCodeMap = new HashMap<Byte,String>();


    public static void main(String[] args) {
        //压缩
       fileZip("E:\\Test\\1.png","E:\\Test\\ZZZ.zip");
       //解压
        unFileZip("E:\\Test\\ZZZ.zip","E:\\Test\\2.png");
    }

    /**
     * 解压文件
     * @param reader
     * @param writer
     */
    public static void unFileZip(String reader ,String writer){
            FileInputStream in = null;
            FileOutputStream out = null;
            ObjectInputStream inobj = null;
            try {
                in = new FileInputStream(reader);
                inobj = new ObjectInputStream(in);
                out = new FileOutputStream(writer);
                byte[] bytes = (byte[]) inobj.readObject();
                Map<Byte,String> map = (Map<Byte,String>)inobj.readObject();
                bytes=unhuffmanZip(bytes,map);
                out.write(bytes);
                System.out.println("解压成功");

            }catch (IOException | ClassNotFoundException e ){
                System.out.println(e.getMessage());
            }
    }
    /**
     * 压缩文件
     * @param reader
     * @param writer
     */
    public static void fileZip(String reader ,String writer){
    FileInputStream in = null;
    FileOutputStream out = null;
    ObjectOutputStream objectin = null;
    try {
        in = new FileInputStream(reader);
        out = new FileOutputStream(writer);
        objectin = new ObjectOutputStream(out);
        byte[] bytes = new byte[in.available()];
        bytes  = in.readAllBytes();
        bytes = huffmanZip(bytes);//获取压缩数据
        objectin.writeObject(bytes);
        objectin.writeObject(huffnanCodeMap);
        System.out.println("数据压缩成功");
    }catch (IOException e){
        System.out.println(e.getMessage());
    }

}
    /**
     * 解压压缩
     * @param bytes
     * @return
     */
    public static byte[] unhuffmanZip(byte[] bytes,Map<Byte,String> map){
       return unZip(bytes,map);
    }

    /**
     * 压缩数据
     * @param bytes  字节数组
     * @return
     */
    //10011110
    public static byte[] huffmanZip(byte[] bytes){
        List<NodeCode> list = getNodes(bytes);//根据list创建赫夫曼编码表
        NodeCode node = gethuffman(list);//获取赫夫曼树
//        node.pre();
//        System.out.println(huffnanCodeMap.size());

        getCodes(node,"", new StringBuilder());//获取赫夫曼码表
        for(Map.Entry<Byte,String> eee:huffnanCodeMap.entrySet()){
            System.out.println((char)(byte)eee.getKey()+"--------"+eee.getValue());
        }
        byte[] b = zip(bytes,huffnanCodeMap);//压缩（根据码表和字节数组获得压缩后的字节数组）
//        System.out.println(Arrays.toString(b));
        return b;
    }
    /**
     * 解压
     * @param bytes
     */
    public static byte[] unZip(byte[] bytes,Map<Byte,String> map) {
        byte by = bytes[bytes.length-1];
        int byint =by;
        String len =Integer.toBinaryString(byint);
        StringBuilder buliod = new StringBuilder();
        StringBuilder buil = new StringBuilder();
        List<Byte> list = new ArrayList<Byte>();
        for(int i = 0;i<bytes.length-1;i++){
            if(i==bytes.length-2&&byint!=0){
                buliod.append(bytetobitString(byint,bytes[i]));
                break;
            }
            buliod.append(bytetobitString(null,bytes[i]));
        }
//        System.out.println(buliod);
        //反转map集合
        Map<String,Byte> haffmanmap = new HashMap<String, Byte>();
        for(Map.Entry<Byte,String>m:map.entrySet()){
            haffmanmap.put(m.getValue(),m.getKey());
        }
        int index=0;
        for (int i = 0;i<buliod.length();i=index){
            index=i;
            while (true){
            if(haffmanmap.get(buliod.substring(i,index))==null){
                index++;
            }else {
                list.add(haffmanmap.get(buliod.substring(i,index)));
                break;
            }}

        }
        byte[] bytee = new byte[list.size()];
        for(int i =0;i<list.size();i++){
            bytee[i]=list.get(i);
        }
//       System.out.println(buil);
        return bytee;
    }

    /**
     * 获取字节二进制
     * @param bytes
     * @param inter 字节个数null表示八个
     */
    public static String bytetobitString(Integer inter,byte bytes) {
        int i;
        if(inter==null){
            i = bytes;
            i|=256;
            String str = Integer.toBinaryString(i);
            String sssss = str.substring(str.length()-8);
            return sssss;
        }else{
            int in = inter;
            i = bytes;
            i|=256;
            String str = Integer.toBinaryString(i);

            return str.substring(str.length()-inter);
        }
    }
    /**
     * 根据赫夫曼码表对字节数组压缩
     * @param bytes
     * @param map
     */
    public static byte[] zip(byte[] bytes,Map<Byte,String> map){
        //利用Stringnulider将bytes转成赫夫曼编码对应的字符串
        StringBuilder sb = new StringBuilder();
        for(byte b:bytes){
            sb.append(map.get(b));
        }
        //字节数组长度
        int len = 0;
        byte bit = 0;
        byte[] byteCode;
        if(sb.length()%8==0){
            len = sb.length()/8+1;
            byteCode = new byte[len];
            byteCode[len-1]=0;
        }else {
           int i =sb.length()%8;
            bit =(byte)i;
            len =sb.length()/8+2;
            byteCode = new byte[len];
            byteCode[len-1]=bit;
        }
        int index=0;
        for(int i = 0;i<sb.length();i+=8){
            String ss="";
            if(i+8>sb.length()){
                  ss = sb.substring(i);
            }else{
                ss = sb.substring(i,i+8);}
            int a = Integer.parseInt(ss,2);//将压缩后的二进制转换成对应的十进制数字
            byteCode[index]=(byte)a;
            index++;
        }
//        System.out.println("压缩后");
//        for(byte bb:byteCode){
//            System.out.println(bb);
//        }
        return byteCode;
}

    /**
     * 创建赫夫曼码表
     * @param flag 表示向左 1 表示向右
     * @param
     */
    public static void getCodes(NodeCode node,String flag,StringBuilder str){
        StringBuilder bulid = new StringBuilder(str);
        bulid.append(flag);
        if(node.getLeft()!=null){
            getCodes(node.getLeft(),"0",bulid);}
        if(node.getRight()!=null){
            getCodes(node.getRight(),"1",bulid);}
        if(node.getKey()!=null){
            huffnanCodeMap.put(node.getKey(),bulid.toString());
        }
    }
    /**
     * 接受字节数组
     * 返回list   {key='a',val=5;key'b',val=4}
     * key表示字母
     * val表示该字母多少个
     * @return
     */
    public static List<NodeCode> getNodes(byte[] bytes){
        List<NodeCode> list = new ArrayList<NodeCode>();
        Map<Byte,Integer> map = new HashMap<Byte,Integer>();
        for(byte b:bytes){
            Integer i=map.get(b);
            if(map.get(b)==null){
                map.put(b,1);
            }else {
                map.put(b,i+1);
            }
        }
        for(Map.Entry<Byte,Integer> m: map.entrySet()){
            list.add(new NodeCode(m.getKey(),m.getValue()));
        }
//        for(NodeCode node:list){
//            System.out.println((char) (byte)node.getKey()+"  "+node.getVal());
//        }
        return list;
    }
    /**
     * 创建赫夫曼数
     * @return root节点
     */
    public static NodeCode gethuffman(List<NodeCode> list){
        while(list.size()>1){
            Collections.sort(list);
            NodeCode left = list.get(0);
            NodeCode right = list.get(1);
            NodeCode node = new NodeCode(null,left.getVal()+right.getVal());
            node.setLeft(left);
            node.setRight(right);
            list.remove(left);
            list.remove(right);
            list.add(node);
        }
        return list.get(0);
    }

}

/**
 * key表示字母
 * val表示该字母多少个
 *
 */
//创建node待数据和权值
class NodeCode implements Comparable<NodeCode>{
    private Byte key;//键
    private int val;//值
    private NodeCode left ;
    private NodeCode right;
    NodeCode(Byte key,int val){//构造
        this.key=key;
        this.val=val;
    }
    //前序遍历
    public void pre(){
        System.out.println(this);
        if(this.left!=null){
            this.left.pre();
        }
        if(this.right!=null){
            this.right.pre();
        }
    }
    public Byte getKey() {
        return key;
    }
    public void setKey(Byte key) {
        this.key = key;
    }
    public int getVal() {
        return val;
    }
    public void setVal(int val) {
        this.val = val;
    }

    public NodeCode getLeft() {
        return left;
    }
    public void setLeft(NodeCode left) {
        this.left = left;
    }
    public NodeCode getRight() {
        return right;
    }
    public void setRight(NodeCode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        if(key!=null){
            return "NodeCode{" +
                    "key=" + (char)(byte)key +
                    ", val=" + val +
                    '}';}else  return "NodeCode{" +
                "key=" + key +
                ", val=" + val +
                '}';
    }

    @Override
    public int compareTo(NodeCode o) {
        return val-o.val;
    }
}
